package com.leetcode.array;

import java.util.Arrays;
/**
 * Given an array of size n, find the majority element. 
 * The majority element is the element that appears more 
 * than ⌊ n/2 ⌋ times.

   You may assume that the array is non-empty and the 
   majority element always exist in the array.
   
 * @author Adiy
 *
 */
public class MajorityElement {

	public static void main(String[] args) {
		int nums[]={1,5,2,5,3,5,4,5,5,5,6,5,7,5};
		int majority=majorityElement(nums);
		System.out.println("超过n/2的元素是："+majority);
	}

	public static int majorityElement(int[] nums){
		Arrays.sort(nums);
		int last=nums.length-1;
		int count=1;
		while(last>0){
			if(nums[last-1]==nums[last]){
				count++;
			}else{
				if(count>nums.length/2){
					break;
				}
				count=1;
			}
			last--;
		}
		
		return nums[last];
	}
}
